class node(object):
   left, right, data = None, None, 0

   def __init__(self, data):
      self._id = 0
      self.left = None
      self.right = None
      self.data = data

   def setid(self, dataid):
      if dataid:
         self._id = dataid

   def __int__(self):
      return int(self._id)

   def __str__(self):
      return str(self.data)

   def __unicode__(self):
      return unicode(str(self))

   def __repr__(self):
      return repr(str(self))

class bintree(object):
   def __init__(self):
      self.root = None

   def add(self, data, did = 0):
      retval = node(data)
      if did:
         retval.setid(did)

      return retval

   def insert(self, root, data, did):
      if root == None:
         return self.add(data, did)
      else:
         if int(data) <= int(root.data):
            root.left = self.insert(root.left, data, did)
         else:
            root.right = self.insert(root.right, data, did)

      return root

   def lookup(self, root, target):
      retval = None
      if root:
         if int(target) == int(root.data):
            retval = root
         else:
            if int(target) < int(root.data):
               retval = self.lookup(root.left, target)
            else:
               retval = self.lookup(root.right, target)

      return retval

   def minval(self, root):
      while (root.left != None):
         root = root.left

      return root

   def maxdepth(self, root):
      retval = None
      root = root
      if root == None:
         retval = 0
      else:
         ldepth = self.maxdepth(root.left)
         rdepth = self.maxdepth(root.right)
         retval = max(ldepth, rdepth) + 1

      return retval

   def size(self, root):
      retval = 0
      if root:
         retval = self.size(root.left) + 1 + self.size(root.right)

      return retval

   def puts(self, root, direction = 1):
      if root == None:
         pass
      else:
         if direction == 1:
            self.puts(root.left)
            print root.data,
            self.puts(root.right)
         elif direction == 0:
            self.puts(root.right)
            print root.data,
            self.puts(root.left)

class tree(object):
   def __init__(self):
      self._tree = bintree()
      self._root = self._tree.add(0)

   def insert(self, data, did = 0):
      return self._tree.insert(self._root, data, did)

   def lookup(self, data):
      return self._tree.lookup(self._root, data)

   def __len__(self):
      return self._tree.size(self._root)

   minval = property(fget = lambda self: self._tree.minval(self._root))
   depth = property(fget = lambda self: self._tree.maxdepth(self._root))

